package LeetCode._01算法入门.day01二分查找;

import org.junit.Test;



/**
 * @author 挚爱之夕
 * @date 2022-02-20 - 02 - 20 - 20:30
 * @Description 给定一个n个元素有序的（升序）整型数组nums
 * 和一个目标值target，写一个函数搜索nums中的 target，
 * 如果目标值存在返回下标，否则返回 -1。
 * @Version 简单
 */
public class _704二分查找 {
    static int[] nums = {-1,0,3,5,9,12};
    static int target = 0;
    @Test
    public void solve1(){//自己写的
        int index = binarySearch(nums, 0, nums.length - 1, target);
        System.out.println(index);
    }

    /**
     * 在升序的数组中寻找目标下标
     * @param nums  数组
     * @param left 左边起始下标
     * @param right 右边起始下标
     * @param target 目标值
     * @return 没找到返回-1，否则返回目标下标
     */
    private int binarySearch(int[] nums, int left, int right, int target){//递归
        if(left > right) // 找不到
            return -1;
        int midIndex = left + ((right - left) >> 2);
        /*
        不用（left+right）/2形式，当left和right都是int，两个值的和超过int限定大小，
        那么left+right就会发生溢出，所以应该用left+(right-left)/2来防止求中值时候发生数据溢出
         */
        if(nums[midIndex] == target){//找到
            return midIndex;
        }else if(nums[midIndex] > target){//在左边
            return binarySearch(nums, left, midIndex - 1, target);
        }else{//在右边
            return binarySearch(nums, midIndex + 1, right, target);
        }
    }
    @Test
    public void solve2(){
        int index = iteration(nums, 0, nums.length - 1, target);
        System.out.println(index);
    }

    public int iteration(int[] nums, int left, int right, int target){   //迭代
        while(left <= right){
            int midIndex = (left + right) / 2;
            int midNumber = nums[midIndex];
            if(midNumber == target){
                return midIndex;
            }else if(midNumber > target){
                right = midIndex - 1;
            }else{
                left = midIndex + 1;
            }
        }
        return -1;
    }
}
